package com.cty.twentyNinethDay;

import java.util.HashMap;
import java.util.Stack;

/*
给定两个整数数组 preorder 和 inorder ，
其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，
请构造二叉树并返回其根节点。
*/
public class Q_47 {

    // 力扣官方题解 方法一:递归
    /*
    * 思路:
    *   首先用一个hash表记录中序遍历数组的值(键) 和 下标(值)
    *   将数组分割(分割的下标 是本次递归的根节点) 分割之后(逻辑分割)
    *   创建根节点 在进行递归 左子节点为前序子数组的第一个节点
    *   (逻辑分割) 再找到分割下标 继续递归创建 返回即可
    *   时间复杂度O(n) 空间复杂度O(n)
    * */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int preLen = preorder.length;
        int inLen = inorder.length;

        if (preLen != inLen) {
            throw new RuntimeException("Incorrect input data");
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        // 先将中序遍历的值存入哈希表中 方便我们定位
        for (int i = 0;i < inLen;i++) {
            map.put(inorder[i],i);
        }
        return buildTree(preorder,0,preLen - 1,map,0,inLen - 1);
    }

    private TreeNode buildTree(int[] preorder, int preStart, int preEnd,
                               HashMap<Integer, Integer> map, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        //创建头节点
        TreeNode root = new TreeNode(preorder[preStart]);
        // 获得头节点在中序遍历中的坐标
        int pIndex = map.get(preorder[preStart]);
        // 递归的定义左右节点 pIndex - inStart = x - preStart
        root.left = buildTree(preorder,preStart + 1,pIndex - inStart + preStart,map,inStart,pIndex - 1);
        root.right = buildTree(preorder,pIndex - inStart + preStart + 1,preEnd,map,pIndex + 1,inEnd);
        return root;
    }

    //力扣官方题解 方法二:迭代
    /*
    * 思路:
    *   首先创建根节点 压入栈中
    *   先序遍历: 根左右 中序遍历:左根右
    *   中序遍历根和左子节点是相反的
    *   我们可以利用栈（具有反向遍历的性质）
    *   我们遍历先序数组 用一个指针指向中序
    *   遍历数组的开始，判断栈顶的元素是
    *   否和遍历的当前元素是否相同 不相同
    *   则挂在栈顶元素的左侧 压入栈中
    *   因为中序遍历数组是二叉树中最左边的元素
    *   遍历的当前节点 也是栈顶(也就是上一个元素)
    *   的左子节点 当前值相同时则说明 这个树的左
    *   子节点 全部被挂上 则出栈寻找 当前节点的
    *   父元素 当前节点为父节点的右子节点
    *   时间复杂度O(n) 空间复杂度O(n)
    **/
    public TreeNode buildTree2(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) return null;
        // 创建一个头节点
        Stack<TreeNode> stack = new Stack<>();
        // 创建头节点
        TreeNode root = new TreeNode(preorder[0]);
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length;i++) {
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorder[i]);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    inorderIndex++;
                    node = stack.pop();
                }
                node.right = new TreeNode(preorder[i]);
                stack.push(node.right);
            }
        }
        return root;
    }
}
